Fast subgoaling for pathfinding via realtime search,” in ICAPS, 2011. Nathan Sturtevant is Assistant Professor in the Computer Science Department at the University of Denver. His scientific research focuses on Artificial Intelligence and search in single

Real-time heuristic search is a standard approach to pathfind-ing when agents are required to make decisions in a bounded, very short period of time. An assumption usually made in the development and evaluation of real-time algorithms is that the environment is unknown. Nevertheless, in many in-teresting applications such as pathfinding for automnomous characters in video games, the environment is known in ad-vance. Recent real-time search algorithms such as D LRTA* and kNN LRTA * exploit knowledge about the environment while pathfinding under real-time constraints. Key to those algorithms is the computation of subgoals in a preprocessing step. Subgoals are subsequently used in the online planning phase to obtain high-quality solutions. Preprocessing in those algorithms, however, requires significant computation. In this paper we propose a novel preprocessing algorithm that gener-ates subgoals using a series of backward search episodes car-ried out from potential goals. The result of a single backward search episode is a tree of subgoals that we then use while planning online. We show the advantages of our approach over state-of-the-art algorithms by carrying out experiments on standard real-time search benchmarks